package com.origin.niuke.bit_operation;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * NC220 重复的DNA序列
 * 算法：滑动窗口 + 位运算
 * @author yezh
 * @date 2022/11/23 22:50
 */
public class NC220 {

    static final Map<Character, Integer> bin = new HashMap<>(4);

    static {
        bin.put('A', 0);
        bin.put('C', 1);
        bin.put('G', 2);
        bin.put('T', 3);
    }

    static final int L = 10;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param DNA string字符串 1
     * @return string字符串一维数组
     */
    public String[] repeatedDNA(String DNA) {
        // write code here
        int len = DNA.length();
        if (len <= L) return new String[0];
        int x = 0;
        for (int i = 0; i < L; i++) x = (x << 2) | bin.get(DNA.charAt(i));
        Map<Integer, Integer> map = new HashMap<>();
        map.put(x, 1);
        List<String> ans = new ArrayList<>();
        for (int i = 1; i <= len - L; i++) {
            x = ((x << 2) | bin.get(DNA.charAt(i + L - 1))) & ((1 << L * 2) - 1);
            map.put(x, map.getOrDefault(x, 0) + 1);
            if (map.get(x) == 2) ans.add(DNA.substring(i, i + L));
        }
        return ans.toArray(new String[0]);
    }

}
